package com.uxsino.commons.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.function.Function;

/**
 * To detect circular reference chain.
 * all tested node is cached internally, call {@link reset} before us it on another graph
 * 
 *
 *
 * @param <T> Object Type
 * @param <K> the Key type of the object
 */
public class CycleDetector<T> {

    private Function<T, Iterator<T>> refFunction;

    /**
     * cach objects lead to no circle 
     */
    private Set<T> knownGood = new HashSet<>();

    /**
     * only one know circle for each node, multiple path ignored
     */
    private Map<T, List<T>> knownCircle = new HashMap<>();

    public CycleDetector(Function<T, Iterator<T>> refFunction) {
        this.refFunction = refFunction;
    }

    /**
     * test if a node is involved in a circle
     * 
     * @param start
     * @return returns a circle found, or null
     */
    public List<T> detect(T start) {
        if (detect(start, new Stack<T>())) {
            return knownCircle.get(start);
        }
        return null;
    }

    private boolean detect(T src, Stack<T> checkingPath) {

        if (knownGood.contains(src))
            return false;

        if (knownCircle.containsKey(src)) {
            return true;
        }
        if (checkingPath.contains(src)) {

            ArrayList<T> circle = new ArrayList<>(checkingPath);

            checkingPath.forEach(node -> knownCircle.put(node, circle));
            return true;
        }
        Iterator<T> itDest = refFunction.apply(src);

        if (itDest == null) {
            knownGood.add(src);
            return false;
        }

        checkingPath.push(src);
        while (itDest.hasNext()) {
            T t = itDest.next();

            if (detect(t, checkingPath)) {
                checkingPath.pop();
                return true;
            }
        }
        checkingPath.pop();
        knownGood.add(src);
        return false;
    }

    /**
     * clean the cached result
     */
    public void reset() {
        knownCircle.clear();
        knownGood.clear();
    }
}
